matematikafandomcom_bs-20200216-history
Prošireni Euklidov algoritam
Prošireni Euklidov algoritam, pored pronalaženja najvećeg zajedničkog djelioca cijelih brojeva a'' i ''b, što radi obični Euklidov algoritam, takođe nalazi cijele brojeve h'' i ''u (od kojih je uglavnom jedan negativan) koji zadovoljavaju Bezuov stav: : ax+by=nzd(a,b) Prošireni Euklidov algoritam je posebno koristan kada su a'' i ''b uzajamno prosti, pošto je h'' modularni multiplikativni inverz od ''a po modulu b'', a ''y je modularni multiplikativni inverz od b'' po modulu ''a. Ovo ima značaj u izračunavanju ključa u RSA algoritmu za šifrovanje javnog ključa; nalaženje celobrojnog eksponenta za dešifrovanje d'' koji je modularni multiplikativni inverz izabranog eksponenta ''e po modulu φ(n), gde su e i φ(n)''uzajamno prosti. Neformalna formulacija algoritma Da bismo ilustrovali proširenje Euklidovog algoritma, razmotrimo izračunavanje nzd(120, 23), koji je prikazan u tabeli. Primijetimo da je količnik u svakom dijeljenju zabilježen kao i ostatak. U ovom slučaju, djelilac u posljednjem redu (koji je jednak 1) nam govori da je nzd 1; to jest, 120 i 23 su uzajamno prosti (takođe se nazivaju i relativno prosti). Zbog jednostavnosti, izabrani primjeri su par uzajamno prostih; ali u opštijem slučaju nzd-a koji nije 1, ovo slično funkcioniše. Postoje dva metoda u nastavku, od kojih oba koriste algoritam cjelobrojnog dijeljenja kao podpostupak, od kojih će svaki biti zasebno diskutovan. Iterativna metoda Ovaj metod računa izraze oblika r_i=ax_i+by_i za ostatak u svakom koraku i Euklidovog algoritma. Svaki uzastopni broj r_i može biti zapisan kao ostatak pri dijeljenju prethodna dva takva broja, čiji ostatak može biti izražen koristeći cio količnik q_i tog dijeljenja prema formuli: r_i=r_{i-2}+q_ir_{i-1} Kada se zamijene vrijednosti, ovo daje: : r_i = (ax_{i-2} + by_{i-2}) - q_i (ax_{i-1} + by_{i-1}),\, što može da se zapiše kao : r_i = a(x_{i-2} - q_i x_{i-1}) + b(y_{i-2} - q_i y_{i-1}).\, Prve dvije vrijednosti su polazni argumenti za algoritam: :: r_1 = a = a\times1 + b\times0\, : r_2 = b = a\times0 + b\times1.\, Dakle, početni koeficijenti su ''x1 = 1, y1 = 0, x2 = 0, i y2 = 1, a drugi su dati kao : x_i = x_{i-2} - q_i x_{i-1},\, : y_i = y_{i-2} - q_i y_{i-1}.\, Izraz za poslednji ne-nula ostatak daje željeni rezultat, pošto ovaj metod računa svaki ostatak u odnosu na a'' i ''b, kao što je i željeno. Primjer: izračunati NZD od 120 i 23 Računanje teče prema narednoj tabeli: U poslednjem redu stoji 1 = 120 × −9 + 23 × 47, što je traženo rešenje: x'' = −9 i ''y = 47. Pošto je NZD 1, ovo takođe znači da 47 daje multiplikativni inverz od 23 po modulu 120, a takođe po modulu 23, -9 (ili 14, koji predstavljaju isti element) daje multiplikativni inverz od 120 (ili, ekvivalentno, od 5). : 47 × 23 ≡ 1 (mod 120) i takođe −9 × 120 ≡14 × 5 ≡ 1 (mod 23). Da bi cio broj a'' bio invertibilan po modulu ''b, potrebno je da a'' i ''b budu uzajamno prosti, tako da, kada bi se pronašao NZD veći od 1, moglo bi se zaključiti da takav modularni inverz ne postoji. Primjetimo da su jednačine koje definišu vrijednosti za xi nezavisne od jednačina koje definišu vrijednosti yi, i da Bezuov identitet na kraju: : r_k=ax_k+by_k dozvoljava dedukciju yk, kada znamo xk. Stoga možemo izostaviti vrednosti yi iz računanja (mada mogu biti korisne za proveru računskih grešaka). Ovo je naročito važno za primene, poput modularnog inverza, koje zahtevaju vrednost samo jednog Bezuovog koeficijenta. Rekurzivna metoda Ovaj metod pokušava da riješi originalnu jednačinu direktno, redukovanjem djelioca i djeljenika postepeno, od prvog do poslednjeg reda, što zatim može biti zamijenjeno trivijalnom vrijednošću i može da funkcioniše unazad u traganju za rješenjem. Razmotrimo originalnu jednakost: Primijetimo da jednakost ostaje neizmenjena nakon razlaganja originalnog dijeljenika u smislu djelioca sa ostatkom, i pregrupisavanja uslova. Ukoliko imamo rješenje jednakosti u drugom redu, onda možemo da idemo unazad i tražimo h'' i ''u kao što je i traženo. Iako još uvijek nemamo rješenje za drugi red, primijetimo kako magnituda uslova opada (120 i 23 u 23 i 5). Stoga, ako nastavimo ovo da primjenjujemo, na kraju ćemo doći do poslednjeg reda, koji očigledno ima (1, 0) kao trivijalno rješenje. Onda možemo da idemo unazad i postepeno nalazimo h'' i ''u. U svrhu objašnjavanja ovog metoda, neće biti prikazan čitav postupak. Umjesto toga, neki koraci koji se ponavljaju će biti opisani da bi se prikazao princip koji stoji u pozadini ove metode. Počnimo tako što ćemo ponovo ispisivati redove iz prve tabele koristeći algoritam dijeljenja, koncentrišući se na djeljenik ovog puta (pošto ćemo deljenik zamjenjivati). Tablična metoda Tablični metod, takođe poznat i kao "Magična kutija", je vjerovatno najjednostavniji metod koji se može obaviti pomoću olovke i papira. Sličan je iterativnom metodu, mada ne zahtjeva direktno korišćenje algebre. Neka NZD(a,b) označava ostatak r u dijeljenju a=bq+r . Osnovna ideja je da razmišljamo o lancu jednakosti : NZD(a,b)=NZD(b, ostatak(a,b))=...=NZD(c,1) kao o sekvenci delilaca (a,b) ostatak (a,b), ...., 1. U postojećem primjeru imamo sekvencu 120, 23, 5, 3, 2, 1. Bilo koji element u ovom lancu se može zapisati kao linearna kombinacija originalnih a'' i ''b, a što je najznačajnije, poslednji element NZD(a,b) , može biti ovako zapisan. Tablični metod uključuje održavanje tabele za svakog djelioca, zapisane kao linearna kombinacija. Algoritam počinje sljedećom tabelom: Elementi u d koloni tabele će biti djelioci u sekvenci. Svako d_i se može predstaviti kao linearna kombinacija a i vrijednosti su očigledne u prva dva reda tabele, i predstavljaju upravo a''' i '''b. Da bismo izračunali d_i za bilo koje i>2 , primjetimo da : d_i= ostatak ' (d_{i-2},d_{i-1}) Pretpostavimo d_i= d_{i-2}- k_{i-1}d_{i-1}) . Onda mora biti : d_i=x_ia+y_ib Ovo je lako algebarski potvrditi jednostavnom zamjenom. Zapravo, obavljanje tabličnog metoda je jednostavnije nego što se to da zaključiti iz gorenavedenih jednakosti. Za nalaženje trećeg reda u tabeli u primeru, samo primetimo da se 120 podeljeno sa 23 pojavljuje 5 puta sa ostatkom. To nam daje ''k, multiplikativni faktor za ovaj red. Sada, svaka od vrednosti u tabeli je vrednost dva reda iznad nje, minus k puta vrednost odmah ispod nje. Ovo korektno vodi do : x_3=1-5*0=1 : y_3=0-5*1=-5 i : d_3=120-5*23=5 Nakon ponavljanja ovog metoda u cilju nalaženja svakog reda tabele (primjetimo da su ostatak zapisan u tabeli i multiplikativni faktor dva različita broja!), konačne vrijednosti za '''x i y''' će riješiti ax+by=NZD(a,b) Ovaj metod je jednostavan i zahtjeva samo ponovljenu primjenu jednog pravila, i daje odgovor u poslednjem redu bez traganja unazad. Primjetimo takođe da ako imamo namjeru da pronađemo modularni inverz za a'' po modulu ''b i dobijemo negativno h'', treba da dodamo modul ''b h''-''u da bismo ga doveli u opseg. Ovo ne utiče na validnost rješenja, pošto imamo a(x+b)+b(y-a)=ax+by Formalni opis algoritma Iterativna metoda Prema rutini algebre o proširenju i grupisanju kao uslovima (pogledati poslednju sekciju), dobijen je sljedeći algoritam za iterativnu metodu: # Primjeniti Euklidov algoritam, i postaviti qn (n počinje od 1) kao konačnu listu količnika u dijeljenju. # Inicijalizovati x0, x1 na 1, 0, i y0, y1 na 0,1. ## Zatim za svako i'' dokle god je ''qi definisano, ## Izračunati xi+1 = xi-1 − qixi ## Izračunati yi+1 = yi−1 − qiyi ## Ponavljati gore navedeno nakon povećanja vrijednosti i'' za 1 # Odgovori su od drugog do poslednjeg od ''xn i yn. Pseudo-kod za ovaj metod je prikazan ispod: '''function prosireni_nzd(a, b) x := 0 poslednji_x := 1 y := 1 poslednji_y := 0 while b ≠ 0 kolicnik := a div b (a, b) := (b, a mod b) (x, poslednji_x) := (poslednji_x - kolicnik*x, x) (y, poslednji_y) := (poslednji_y - kolicnik*y, y) return (poslednji_x, poslednji_y) Dodatni koraci su neophodni kada radimo sa negativnim a'' i/ili ''b. Rekurzivna metoda Rješavajući opšti slučaj jednakosti u poslednjoj odgovarajućoj sekciji, naredni algoritam daje rješenje. Ako je dat bilo koji par nenegativnih cijelih brojeva a'' i ''b, on pronalazi cjelobrojne vrijednosti h'' i ''u takve da je ax + by ''nenegativno i deli ''a i b'', što implicira da je to najveći zajednički djelilac za ''a i b''. # Ako je ''b = 0, algoritam se završava, a kao povratnu vrijednost vraća x'' = 1, ''y = 0. # Inače: #* Odrediti količnik q'' i ostatak ''r dijeljenjem a'' sa ''b koristeći algoritam cjelobrojnog dijeljenja #* Zatim rekurzivno pronaći koeficijente s'', ''t takve da bs + rt dijeli i b'' i ''r. #* Konačno, algoritam vraća rješenje x'' = ''t, i y'' = ''s − qt. Ovo se u pseudo kodu može zapisati ovako: function prosireni_nzd(a, b) if b'' 0 '''return' (1, 0) else (q'', ''r) := podeli (a'', ''b) (s'', ''t) := prosireni_nzd(b'', ''r) return (t'', ''s - q'' * ''t) Ovim pretpostavljamo da postoji postupak dijeljenja koji vraća (količnik, ostatak) par (moglo bi se staviti q'' := ''a divb'', a zatim ''r = a'' − ''b * q''). Dokaz korektnosti Neka su ''a i b'' nenegativni cijeli brojevi. Želimo da dokažemo da se algoritam završava, i vraća (''h, u'') takve da ''ax + by dijeli i a'' i ''b. Nastavljamo indukcijom po b''. * Ako je ''b = 0, algoritam odmah staje sa izvršavanjem sa h'' = 1 i ''u = 0, tako da ax + by = a''; ovo je očigledno nenegativno i dijeli i ''a i 0 (jer je a0 = 0). * Inače, neka su q'', ''r dobijeni dijeljenjem a'' sa ''b kao u opisu algoritma, tako da a'' = ''bq + r'' i ''r < b'' prema svojstvima Euklidovog dijeljenja. ** Nejednakost ''r < b'' znači da možemo da primjenimo induktivnu pretpostavku za (''b,r'') na mestu (''a,b''), i ovo nam garantuje da se rekurzivna primena završava. ** Neka su (''s,t'') vrijednosti koje vraća; prema indukciji znamo da je ''bs + rt nenegativno i dijeli i b'' i ''r. ** Sada algoritam vraća x'' = ''t i y'' = ''s − qt. Imamo ax + by = at + b''(''s − qt) = bs + (a'' − ''bq)t'' = ''bs + rt, što je (još uvijek) nenegativno i dijeli i b'' i ''r. Isti broj stoga dijeli r'' + ''bq = a'', čime se dokaz završava. Dokaz pokazuje da se rekurzivni algoritam može prilagoditi za rad sa proizvoljnim cijelim brojevima ''a, b ''neznatnom modifikacijom: u završnom slučaju ''b = 0 bi trebalo da ispita znak od a'', i ako je negativan vraća ''h = -1, umjesto h'' = 1, da bi se osiguralo da ''ax + by uvijek bude nenegativna vrijednost. Ovim se pretpostavlja da izabrani algoritam dijeljenja funkcioniše ako su a'' i/ili ''b negativni, i osigurava da je |''r''| < |''b''| u svim slučajevima (uobičajena specifikacija Euklidovog dijeljenja zapravo zahteva da r'' bude nenegativno, ali ovo nije neophodno u dokazu, kao što jeste sada po rekurenciji po |''b|). Izračunavanje multiplikativnog inverza u konačnom polju Prošireni Euklidov algoritam se takođe može koristiti za računanje modularnog multiplikativnog inverza u konačnom polju. Pseudokod S obzirom da nesvodljiva polinomijalna funkcija f''(''x) definiše polje, i element a''(''x) čiji inverz želimo, oblik algoritma koji odgovara određivanju inverza je dat u nastavku. PAŽNjA: ostatak() i kolicnik() su funkcije drugačije od niski ostatak[] i kolicnik[]. ostatak() se odnosi na ostatak pri dijeljenju dva broja, a kolicnik() na celobrojni količnik pri dijeljenju dva broja. Dijeljenje (sa ostatkom) se mora izračunati pod uslovima polinomijalne aritmetike a ne "normalnih" brojeva. pseudokod: ostatak1 := f''(x) ostatak2 := ''a(x) pomocni1 := 0 pomocni2 := 1 i := 2 while ostataki > 1 i := i + 1 ostataki := ostatak(ostataki-2 / ostataki-1) kolicniki := kolicnik(ostataki-2 / ostataki-1) pomocnii := -kolicniki * pomocnii-1 + pomocnii-2 inverz := pomocnii : Napomena: u nekim konačnim poljima, na primer GF(2n), ), operacije dodavanja (+) i oduzimanja (−) su iste. Kao posljedica, neki algoritmi namjenjeni takvim poljima neće prikazivati znak minus pije : -quotienti. Primjer Na primer, ako se konačno polje GF(28) definiše polinomijalno sa f''(''x) = x''8 + ''x''4 + ''x''3 + ''x + 1, i x''6 + ''x''4 + ''x + 1 = {53}, u big endian heksadecimalnoj notaciji, je element čiji inverz želimo, izvršivši algoritam dobijamo sljedeće: : Napomena: Dodavanje u binarnom konačnom polju je '''XORRobert B Davies (28. 2. 2002). „Exclusive OR (XOR) and hardware random number generators”.'' Prema ovome, inverz je ''x''7 + ''x''6 + ''x''3 + ''x = {CA}, što se može potvrditi množenjem ova dva elementa. Slučaj više od dva broja Možemo riješiti slučaj više od dva broja iterativno. Prvo, pokažemo da NZD(a,b,c)=NZD(NZD(a,b),c). Da bismo dokazali ovo, neka je d=NZD(a,b,c) . Po definiciji nzd-a, je deelilac od '''a i b'''. Prema tome NZD(a,b)=kd za neko '''k . Slično je d''' delilac za '''c tako da je c=jd za neko j. Neka je . Prema našoj konstrukciji u - a, ud/a,b,c, ali pošto je d najveći delilac u -a je jedinica. I pošto je ud =NZD(NZD(a.b).c)rezultat je dokazan. Tako, ako na+mb=NZD(a,b), onda postoje 'x '''i '''y '''takvi da xNZD(a,b)+yc=NZD(NZD(a,b),c) pa će krajnja jednačina biti x(na+mb)+yc=(xn)a+(xm)b+yc=NZD(a.b,c) Da bi primjenili na n brojeva koristimo indukciju :NZD(a1,,a2,...,an)=NZD(a1,NZD(a2,.....,NZD(an-1,an)))...) uz direktno praćenje jednakosti. Reference Literatura Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest & Clifford Stein (2001). ''Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3 of section 31.2: Greatest common divisor. Spoljašnje veze * Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8) Kategorija:Algoritam